I. The algebra of classes.--II. The algebra of propositions. Applications. Numerically definite reasoning.--III-IV. Set Theory.

This paper is dedicated to Alonzo Church, who died in August 1995 after a long life devoted to logic. To Church we owe lambda calculus, the thesis bearing his name and the solution to the Entscheidungsproblem.His well-known book Introduction to Mathematical LogicI, defined the subject matter of mathematical logic, the approach to be taken and the basic topics addressed. Church was the creator of the Journal of Symbolic Logicthe best-known journal of the area, which he edited (...) for several decades This paper is in three sections. The first is written in journalistic style:the story of the life of AlonzoChurch is told, including some of the many anecdotes I have collected from different sources. The secondpart is devoted to his work, but is far from being exhaustive. The last part is more original; in it I attempto show that Church’s great discovery was lambda calculus and that his remaining contributions weremainly inspired afterthoughts in the sense that most of his contributions as well as some of his pupils derivefrom that initial achievement. Included are Kleene’s Recursion Theory and the completeness proof ofHenkin. I have added an appendix in which is presented the typed lambda calculus and a proof of theundecidability of first-order logic. (shrink)

The Church-Turing thesis makes a bold claim about the theoretical limits to computation. It is based upon independent analyses of the general notion of an effective procedure proposed by Alan Turing and Alonzo Church in the 1930''s. As originally construed, the thesis applied only to the number theoretic functions; it amounted to the claim that there were no number theoretic functions which couldn''t be computed by a Turing machine but could be computed by means of some other (...) kind of effective procedure. Since that time, however, other interpretations of the thesis have appeared in the literature. In this paper I identify three domains of application which have been claimed for the thesis: (1) the number theoretic functions; (2) all functions; (3) mental and/or physical phenomena. Subsequently, I provide an analysis of our intuitive concept of a procedure which, unlike Turing''s, is based upon ordinary, everyday procedures such as recipes, directions and methods; I call them mundane procedures. I argue that mundane procedures can be said to be effective in the same sense in which Turing machine procedures can be said to be effective. I also argue that mundane procedures differ from Turing machine procedures in a fundamental way, viz., the former, but not the latter, generate causal processes. I apply my analysis to all three of the above mentioned interpretations of the Church-Turing thesis, arguing that the thesis is (i) clearly false under interpretation (3), (ii) false in at least some possible worlds (perhaps even in the actual world) under interpretation (2), and (iii) very much open to question under interpretation (1). (shrink)

In an attempt to improve upon Alexander Pruss’s work (The principle of sufficient reason: A reassessment, pp. 240–248, 2006), I (Weaver, Synthese 184(3):299–317, 2012) have argued that if all purely contingent events could be caused and something like a Lewisian analysis of causation is true (per, Lewis’s, Causation as influence, reprinted in: Collins, Hall and paul. Causation and counterfactuals, 2004), then all purely contingent events have causes. I dubbed the derivation of the universality of causation the “Lewisian argument”. The Lewisian (...) argument assumed not a few controversial metaphysical theses, particularly essentialism, an incommunicable-property view of essences (per Plantinga’s, Actualism and possible worlds, reprinted in: Davidson (ed.) Essays in the metaphysics of modality, 2003), and the idea that counterfactual dependence is necessary for causation. There are, of course, substantial objections to such theses. While I think a fight against objections to the Lewisian argument can be won, I develop, in what follows, a much more intuitive argument for the universality of causation which takes as its inspiration a result from Frederic B. Fitch’s work (J Symb Logic 28(2):135–142, 1963) [with credit to who we now know was Alonzo church’s, Referee Reports on Fitch’s Definition of value, in: (Salerno (ed.), New essays on the knowability paradox, 2009)] that if all truths are such that they are knowable, then (counter-intuitively) all truths are known. The resulting Church–Fitch proof for the universality of causation is preferable to the Lewisian argument since it rests upon far weaker formal and metaphysical assumptions than those of the Lewisian argument. (shrink)

Alonzo Church provided three criteria for “strict synonymy”, i.e., sameness of semantic content: Alternatives (0), (1), and (2)--in order of increasing course-grainedness of content. On (2) expressions are strictly synonymous iff they are logically equivalent. (1) is a significant improvement over (2). On (1) expressions are synonymous iff they are lambda-convertible. Even on (1), assuming the Millian account of proper names, ‘Tully admires Cicero’ is deemed synonymous with ‘Cicero is self-admiring’. On (0) expressions are strictly synonymous iff they (...) are “synonymously isomorphic” in Church’s sense. A fourth alternative, here called ‘(3)’, has been maintained by several philosophers. On (3) expressions are strictly synonymous iff they are co-intensional. In particular, sentences are strictly synonymous iff they are true with resect to the same possible worlds. This criterion’s notion of content is even more course grained than that of (2). Several objections to (3) are considered. (shrink)

Enligt ett realistiskt synsätt kan ett påstående vara sant trots att det inte ens i princip är möjligt att veta att det är sant. En sanningsteoretisk antirealist kan inte godta denna möjlighet utan accepterar en eller annan version av Dummetts vetbarhetsprincip: (K) Om ett påstående är sant, så måste det i princip vara möjligt att veta att det är sant. Det kan dock förefalla rimligt, även för en antirealist, att gå̊ med på̊ att det kan finnas sanningar som ingen faktiskt (...) vet (har vetat, eller kommer att veta) är sanna. Man kan därför tänka sig att en antirealist skulle acceptera principen (K) utan att därför gå med på den till synes starkare principen: (SK) Om ett påstående är sant, så måste det faktiskt finnas någon som vet att det är sant. Ett mycket omdiskuterat argument – som ytterst går tillbaka till Alonzo Church, men som först publicerades i en uppsats av Frederic Fitch i Journal of Symbolic Logic 1963 – tycks emellertid visa att principen (K) implicerar principen (SK). Anta nämligen att (K) är sann, medan (SK) inte är det. Men om (SK) är falsk, så finns det ett påstående som är sant men som ingen faktiskt vet är sant. Anta nu att p är ett sådant påstående. Låt Kp betyda att någon vet att p är sant. Det galler alltså̊ att p är sant samtidigt som Kp inte är det. Betrakta nu påståendet (p ∧ −Kp). Enligt antagandet är detta påstående sant. Enligt (K) måste det då vara möjligt att någon vet att (p ∧ −Kp). D.v.s., det måste vara möjligt att påståendet K(p ∧ −Kp) är sant. Men i så fall är det också̊ möjligt att påståendet Kp ∧ K−Kp är sant, vilket i sin tur implicerar att det är möjligt att Kp ∧ −Kp är sant, vilket ju är absurt. Således kan inte (K) vara sann samtidigt som (SK) är falsk. Vi tycks således kunna sluta oss till att (K) implicerar (SK). I uppsatsen diskuterar jag några olika sätt att undgå̊ Church-Fitch paradoxala slutsats. Ett tillvägagångssätt är att ersätta kunskapsoperatorn med en hierarki av kunskapspredikat. Ett annat är baserat på distinktionen mellan faktisk och potentiell kunskap och ett förkastande av den vanliga modallogiska formaliseringen av principen (K). Den senare typen av lösning betraktas både från ett realistiskt och ett icke-realistiskt perspektiv. Utifrån denna analys kommer jag fram till slutsatsen att vi, vare sig vi är realister eller antirealister rörande sanning, kan sluta oroa oss för vetbarhetsparadoxen och ändå uppskatta Church-Fitchs argument. (shrink)

Writings, including articles, letters, and unpublished work, by one of the twentieth century's most influential figures in mathematical logic and philosophy. Alonzo Church's long and distinguished career in mathematics and philosophy can be traced through his influential and wide-ranging writings. Church published his first article as an undergraduate at Princeton in 1924 and his last shortly before his death in 1995. This volume collects all of his published articles, many of his reviews, his monograph The Calculi of (...) Lambda-Conversion, the introduction to his important and authoritative textbook Introduction to Mathematical Logic, a substantial amount of previously unpublished work (including chapters for the unfinished second volume of Introduction to Mathematical Logic), and a selection of letters to such correspondents as Rudolf Carnap and W. V. O. Quine. With the exception of the reviews, letters, and unpublished work, these appear in chronological order, for the most part in the format in which they were originally published. Church's work in calculability, especially the monograph on the lambda-calculus, helped lay the foundation for theoretical computer science; it attracted the interest of Alan Turing, who later completed his PhD under Church's supervision. (Church coined the term “Turing machine” in a review.) Church's influential textbook, still in print, defined the field of mathematical logic for a generation of logicians. In addition, his close connection with the Association for Symbolic Logic and his many years as review editor for the Journal of Symbolic Logic are documented in the reviews included here. (shrink)

There is an inconsistency among claims made (or apparently made) in separate articles by Alonzo Church concerning Frege's distinction between sense and denotation taken together with plausible assertions by Frege concerning his notion of ungerade Sinn-i.e., the sense that an expression allegedly takes on in positions in which it has ungerade Bedeutung, denoting its own customary sense. As with any inconsistency, the difficulty can be avoided by relinquishing one of the joint assumptions from which contradiction may be derived. (...) Yet what seems the most plausible resolution, in light of Church's own arguments, involves abandoning the theory of sense and denotation, in the form in which it has been staunchly advocated by both Frege and Church. That theory has come under sustained criticism from several quarters. Whereas the present difficulty supplements the case against the theory, it is unlike more familiar criticisms, since it is not framed from the perspective of an alternative theory (or picture) but is based instead on an internal conflict, and therefore has special force. (shrink)